Trong lý thuyết độ phức tạp tính toán, lớp NP-đầy đủ là một lớp các bài toán quyết định. Một bài toán L là NP-đầy đủ nếu nó nằm trong lớp NP (lời giải cho L có thể được kiểm chứng trong thời gian đa thức) và là NP-khó (mọi bài toán trong NP đều có thể quy về L trong thời gian đa thức).Mặc dù bất kì lời giải nào cho mỗi bài toán đều có thể được kiểm chứng nhanh chóng, hiện chưa có cách nào tìm ra được lời giải đó một cách hiệu quả. Thời gian thực thi của tất cả các thuật toán hiện tại cho những bài toán này đều tăng rất nhanh theo kích thước bài toán. Vì vậy ngay cả những trường hợp có kích thước tương đối lớn đã đòi hỏi thời gian hàng tỷ năm để giải. Do đó, việc xác định xem những bài toán này có thể được giải quyết nhanh chóng hay không (thường gọi là bài toán P so với NP) là một trong những bài toán mở của khoa học máy tính hiện nay.Các bài toán NP-đầy đủ xuất hiện thường xuyên trong thực tế nên, mặc dù chưa có giải thuật trong thời gian đa thức cho chúng, các nhà nghiên cứu vẫn tìm cách giải quyết chúng thông qua các phương pháp khác như thuật toán xấp xỉ, nhân tử hóa, v.v...